package bc;

public class lc547 {
    static class UF{
        int count;
        int[] father;
        public UF(int count) {
            this.count = count;
            father = new int[count];
            for (int i = 0; i < count; i++) {
                father[i] = i;
            }
        }

        public int getCount() {
            return count;
        }
        public int getFather(int i){
            if(i == father[i])
                return i;
            return getFather(father[i]);
        }
        public void uniform(int i, int j){
            int p = getFather(i);
            int q = getFather(j);
            if(p == q)
                return;
            father[p] = q;
            count--;
        }
    }
    public static void main(String[] args) {
        System.out.println(findCircleNum(new int[][]{{1,1,0},{1,1,0},{0,0,1}}));
    }
    public static int findCircleNum(int[][] isConnected) {
        UF uf = new UF(isConnected.length);
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected.length; j++) {
                if(isConnected[i][j] == 1)
                uf.uniform(i, j);
            }
        }
        return uf.getCount();
    }
}
